/**
质因数分解是将一个数分解为若干个质数相乘的形式，这些因数可以重复。比如 30=2 ×3 × 5,
20=2 × 2 ×5,81=3×3×3×3。现在我们将质因数分解之后只出现 2,3,5,7 的数称为Humble Number，
则 20,30,81 均为 Humble Number，而 11,22 不是。前 20 个 HumbleNumber 的序列为
1,2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27。设计一个动态规划算法，求解第 n 个 Humble Number。
*/

#include <stdio.h>
#include <set>

int GetMin(int i, int j){
    return i < j ? i : j;
}

int HumbleNumber(int n) {
    int index[4] = {0,0,0,0};
    int *humble = new int[n];
    humble[0] = 1;
    for(int i = 1; i < n; i++) {
        int a = humble[index[0]] * 2;
        int b = humble[index[1]] * 3;
        int c = humble[index[2]] * 5;
        int d = humble[index[3]] * 7;
        int min = GetMin(a, GetMin(b, GetMin(c, d)));
        if(a == min) index[0]++;
        if(b == min) index[1]++;
        if(c == min) index[2]++;
        if(d == min) index[3]++;
        humble[i] = min;
    }
    return humble[n-1];
}

//效率极差，指数级，弃用
int HumbleNumber2(int n){
    std::set<int> S;//存储已经验证过的Humber Number
    S.insert(1);
    int i = 1, j = 1;//i统计已计算的Humber Number
    while(i < n){
        j ++;
        if(j % 2 == 0 && S.count(j / 2)){
            S.insert(j);
            i++;
            continue;
        }
        if(j % 3 == 0 && S.count(j / 3)){
            S.insert(j);
            i++;
            continue;
        }
        if(j % 5 == 0 && S.count(j / 5)){
            S.insert(j);
            i++;
            continue;
        }
        if(j % 7 == 0 && S.count(j / 7)){
            S.insert(j);
            i++;
            continue;
        }
    }
    return j;
}

int main(){
    int n = 2000;
    printf("%d\n", HumbleNumber(n));
    //printf("%d\n", HumbleNumber2(n));
}
